// 解题思路：
// 第一步：预处理，先逆序字符串，再转化为字符串数组
// 第二步：双循环进行无进位相乘
// 第三步：处理进位
// 第四步：消除前导零

public class LargeNumMultiplication {
    public String solve (String s, String t) {
        // write code here
        int m = s.length();
        int n = t.length();

        StringBuilder ss = new StringBuilder(s);
        StringBuilder tt = new StringBuilder(t);

        char[] sArr = ss.reverse().toString().toCharArray();
        char[] tArr = tt.reverse().toString().toCharArray();

        int[] arr = new int[m + n - 1];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                arr[i + j] += (sArr[i] - '0') * (tArr[j] - '0');
            }
        }

        StringBuilder ret = new StringBuilder();
        int carry = 0;
        int i = 0;
        while(i < m + n - 1 || carry > 0){
            if(i < m + n - 1){
                carry += arr[i];
            }
            ret.append(carry % 10);
            carry /= 10;
            i++;
        }

        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0'){
            ret.deleteCharAt(ret.length() - 1);
        }

        return ret.reverse().toString();
    }

    public String solve2 (String s, String t) {
        // write code here
        if(s.equals("0") || t.equals("0")) return "0";
        int m = s.length();
        int n = t.length();
        int[] arr = new int[m + n - 1];
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();

        for(int i = m - 1; i >= 0; i--){
            for(int j = n - 1; j >= 0; j--){
                arr[i + j] += ((sArr[i] - '0') * (tArr[j] - '0'));
            }
        }

        int i = m + n - 2;
        long carry = 0;
        StringBuilder ret = new StringBuilder();

        while(i >= 0 || carry > 0){
            if(i >= 0) carry += arr[i];
            ret.append(carry % 10);
            carry /= 10;
            i--;
        }

        return ret.reverse().toString();
    }
}
